package main

/*
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity
*/
type ListNode struct {
	val  int
	next *ListNode
}

func mergeKList(lists []*ListNode) *ListNode {
	length := len(lists)
	if length < 1 {
		return nil
	}
	if length == 1 {
		return lists[0]
	}
	num := length / 2
	left := mergeKList(lists[:num])
	right := mergeKList(lists[num:])
	return mergeTwoList(left, right)
}

func mergeTwoList(left *ListNode, right *ListNode) *ListNode {
	if left == nil {
		return right
	}
	if right == nil {
		return left
	}
	if left.val < right.val {
		left.next = mergeTwoList(left.next, right)
		return left
	}
	right.next = mergeTwoList(left, right.next)
	return right
}
